/* 518. 零钱兑换 II */
/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
/* 
    dp[i] 表示金额之和为i 的硬币组合数 目标是求 dp[amount] 
    dp[0] 只有在不选取任何硬币时，金额之和才为0 因此只有一种组合
    对于面额为coin 的硬币 当 coin <= i <= amount 时如果存在一种硬币之和
    等于 i-coin ,则在该硬币组合中增加一个面额为coin的硬币,即可的到一种面额之和
    等于i的硬币组合 
*/
var change = function (amount, coins) {
	const dp = new Array(amount + 1).fill(0)
	/* 初始化边界条件 */
	dp[0] = 1
	for (const coin of coins) {
		for (let i = coin; i <= amount; i++) {
			/* 
                如果选择硬币coins[i] 那么当前硬币的组合数量就有的dp[i-coins[i]]
                如果不选则coins[i]那么当前硬币组合数量 就是 dp[i]
            */
			dp[i] += dp[i - coin]
		}
	}
	return dp[amount]
}
change(5, [1, 2, 5])
